package ua.com.globallogic.basecamp.krasnyanskiy.dds.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class SimpleTree<T extends Comparable> {
    private int size = 0;
    Node<T> root;

    private class Node<T extends Comparable> {
        Node<T> left;
        Node<T> right;
        T value;

        public Node(T value) {
            this.value = value;
        }
    }

    public int size() {
        return size;
    }

    public void insert(T value) {
        if (root == null) {
            root = new Node<T>(value);
            size++;
        } else {
            insert(root, value);
        }
    }

    private void insert(Node<T> node, T value) {
        if (value.compareTo(node.value) < 0) {
            if (node.left != null) {
                insert(node.left, value);
            } else {
                node.left = new Node<T>(value);
                size++;
            }
        } else if (value.compareTo(node.value) > 0) {
            if (node.right != null) {
                insert(node.right, value);
            } else {
                node.right = new Node<T>(value);
                size++;
            }
        }
    }

    public boolean contains(T elem) {
        return contains(root, elem);
    }

    private boolean contains(Node<T> node, T obj) {
        if (node == null) {
            return false;
        } else if (node.value.compareTo(obj) == 0) {
            return true;
        } else if (node.value.compareTo(obj) > 0) {
            return contains(node.left, obj);
        } else {
            return contains(node.right, obj);
        }
    }

    public void delete(T elem) {
        root = deleteNode(root, elem);
        size--;
    }

    private Node deleteNode(Node<T> root, T elem) {
        Node<T> tmp;
        if (elem.compareTo(root.value) < 0)
            root.left = deleteNode(root.left, elem);
        else if (elem.compareTo(root.value) > 0)
            root.right = deleteNode(root.right, elem);
        else {
            if (root.right == null) root = root.left;
            else if (root.left == null)
                root = root.right;
            else {
                tmp = root.left;
                if (tmp.right != null) {
                    while (tmp.right.right != null)
                        tmp = tmp.right;
                    root.value = tmp.right.value;
                    tmp.right = tmp.right.left;
                } else {
                    root.value = tmp.value;
                    root.left = root.left.left;
                }
            }
        }
        return root;
    }

    public void erase() {
        root = null;
        size = 0;
    }

    public List<T> print() {
        List<T> result = new ArrayList<T>();
        doPrint(result);
        return result;
    }

    private void doPrint(List<T> result) {
        LinkedList<Node<T>> list = new LinkedList<Node<T>>();
        Node<T> n = root;
        if (n != null) {
            list.addLast(n);
            while (list.size() != 0) {
                n = list.removeFirst();
                result.add(n.value);
                if (n.left != null) {
                    list.addLast(n.left);
                }
                if (n.right != null) {
                    list.addLast(n.right);
                }
            }
        }
    }
}